// Package _9___II__队列的最大值 main
// @Title _9___II__队列的最大值
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-15 10:08
// @Create  2022-02-15 10:08
package main

import "fmt"

// 如何保证当前队列的最大值出队后，找到下一个最大值

// 使用双端队列，

// 入队： 单队尾元素 < 入队元素？

type MaxQueue struct {
	DataQueue        []int
	OrderDoubleQueue []int // 定义单调双端队列
}

func Constructor() MaxQueue {
	return MaxQueue{
		DataQueue:        []int{},
		OrderDoubleQueue: []int{},
	}
}

func (this *MaxQueue) Max_value() int {
	if len(this.OrderDoubleQueue) == 0 {
		return -1
	}
	// 直接返回单调双端队列的对头元素即可，注意 这里不需要改变单调队列的长度
	return this.OrderDoubleQueue[0]
}

func (this *MaxQueue) Push_back(value int) {
	this.DataQueue = append(this.DataQueue, value) // 数据队列直接尾部追加不管
	// 如果当前值比单调队列的队尾元素要大？  循环删除单调队列的队尾元素 直到val小于队尾
	dLen := len(this.OrderDoubleQueue)
	for dLen > 0 && value > this.OrderDoubleQueue[dLen-1] {
		this.OrderDoubleQueue = this.OrderDoubleQueue[:dLen-1]
		dLen--
	}
	this.OrderDoubleQueue = append(this.OrderDoubleQueue, value)
}

func (this *MaxQueue) Pop_front() int {
	if len(this.DataQueue) == 0 {
		return -1
	}
	popData := this.DataQueue[0]
	this.DataQueue = this.DataQueue[1:]
	// 刚好删除了最大值的情况 并且单调队列也不为空
	if len(this.OrderDoubleQueue) != 0 && popData == this.OrderDoubleQueue[0] {
		this.OrderDoubleQueue = this.OrderDoubleQueue[1:]
	}
	return popData
}

func main() {
	c := Constructor()
	c.Push_back(94)
	fmt.Println(c.DataQueue, c.OrderDoubleQueue)
	c.Push_back(16)
	fmt.Println(c.DataQueue, c.OrderDoubleQueue)
	c.Push_back(89)
	fmt.Println(c.DataQueue, c.OrderDoubleQueue)
	fmt.Println(c.Pop_front())
	fmt.Println(c.DataQueue, c.OrderDoubleQueue)
	c.Push_back(22)
	fmt.Println(c.DataQueue, c.OrderDoubleQueue)
	fmt.Println(c.Pop_front())
	fmt.Println(c.DataQueue, c.OrderDoubleQueue)
}
